package dlut.java;

import java.util.*;
import java.util.stream.Collectors;

public class Solusion {
    public static void main(String[] args) {
        Solusion s1 = new Solusion();
        long start = System.currentTimeMillis();

        int[][] nums = {{1,2,3},{4,5,6},{7,8,9}};
        var result = s1.maxConsecutiveAnswers("TTFTTFTT",1);
        System.out.println(result);

        long end = System.currentTimeMillis();
        System.out.println("abc".equals("ab"+"c"));
        System.out.println(Integer.valueOf(100) ==  Integer.valueOf(100));

    }

    public int maxConsecutiveAnswers(String answerKey, int k) {
        int length = answerKey.length();
        int left = 0, right = 0, maxLen = 1, count = 0;
        while(right < length){
            if (answerKey.charAt(right) == 'F'){
                count ++;
                if (count > k){
                    while (answerKey.charAt(left) == 'T')
                        left++;
                    left++;
                    right++;
                    continue;
                }else{
                    right++;
                    maxLen = Math.max(maxLen, right - left);
                    continue;
                }
            }
            right++;
            maxLen = Math.max(maxLen, right - left);
            continue;
        }
        left = 0; right = 0;  count = 0;
        int maxLen1 = 1;
        while(right < length){
            if (answerKey.charAt(right) == 'T'){
                count ++;
                if (count > k){
                    while (answerKey.charAt(left) == 'F')
                        left++;
                    left++;
                    right++;
                    continue;
                }else{
                    right++;
                    maxLen1 = Math.max(maxLen1, right - left);
                    continue;
                }
            }
            right++;
            maxLen1 = Math.max(maxLen1, right - left);
            continue;
        }
        return Math.max(maxLen, maxLen1);
    }
    public int maxConsecutiveAnswers1(String answerKey, int k) {
        int[] dpT = new int[k+1];
        int[] dpF = new int[k+1];
        int length = answerKey.length();
        int maxLen = 1;
        for (int i = 0; i < length; i++) {
            if (answerKey.charAt(i) == 'T'){
                for (int j = 0; j <= k; j++) {
                    dpT[j]++;
                }
                maxLen = Math.max(maxLen, dpT[k]);
                for (int j = k; j > 0; j--) {
                    dpF[j] = dpF[j-1] + 1;
                }
                dpF[0] = 0;
                maxLen = Math.max(maxLen, dpF[k]);
            }
            if (answerKey.charAt(i) == 'F'){
                for (int j = 0; j <= k; j++) {
                    dpF[j]++;
                }
                maxLen = Math.max(maxLen, dpF[k]);
                for (int j = k; j > 0; j--) {
                    dpT[j] = dpT[j-1] + 1;
                }
                dpT[0] = 0;
                maxLen = Math.max(maxLen, dpT[k]);
            }
        }
        return maxLen;
    }

    /**
     * 304. 二维区域和检索
     * @param matrix
     */
    int[][] sums;
    public void NumMatrix(int[][] matrix) {
        int m = matrix.length;
        if (m > 0) {
            int n = matrix[0].length;
            sums = new int[m + 1][n + 1];
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    sums[i + 1][j + 1] = sums[i][j + 1] + sums[i + 1][j] - sums[i][j] + matrix[i][j];
                }
            }
        }
    }
    public int sumRegion(int row1, int col1, int row2, int col2) {
        return sums[row2 + 1][col2 + 1] - sums[row1][col2 + 1] - sums[row2 + 1][col1] + sums[row1][col1];
    }

    /**
     * 1314. 矩阵区域和
     * @param mat
     * @param k
     * @return
     */
    public int[][] matrixBlockSum(int[][] mat, int k) {
        int m = mat.length;
        int n = mat[0].length;
        int[][] answer = new int[m][n];
        for (int i = 0; i <= k && i < m; i++) {
            for (int j = 0; j <= k && j < n; j++) {
                answer[0][0] += mat[i][j];
            }
        }
        for (int i = 0; i < m; i++) {
            if (i != 0){
                answer[i][0] = answer[i-1][0];
                if (i-k-1 >= 0)
                    for (int j = 0; j <= k && j < n; j++) {
                        answer[i][0] -= mat[i-k-1][j];
                    }
                if (i+k < m)
                    for (int j = 0; j <= k && j < n; j++) {
                        answer[i][0] += mat[i+k][j];
                    }
            }
            for (int j = 1; j < n; j++) {
                answer[i][j] = answer[i][j-1];
                if (j-k-1 >= 0)
                    for (int l = Math.max(0,i-k); l <= i+k && l < m; l++) {
                        answer[i][j] -= mat[l][j-k-1];
                    }
                if (j+k < n)
                    for (int l = Math.max(0,i-k); l <= i+k && l < m; l++) {
                        answer[i][j] += mat[l][j+k];
                    }
            }
        }
        return answer;
    }

    /**
     * 120. 三角形最小路径和
     * @param triangle
     * @return
     */
    public int minimumTotal(List<List<Integer>> triangle) {
        int size = triangle.size();
        int[][] func = new int[size][];
        func[0] = new int[1];
        func[0][0] = triangle.get(0).get(0);
        for (int i = 1; i < size; i++) {
            func[i] = new int[i+1];
            for (int j = 0; j <= i; j++) {
                int temp;
                if (j == 0)
                    temp = func[i-1][j];
                else if (j == i)
                    temp = func[i-1][j-1];
                else
                    temp = Math.min(func[i-1][j], func[i-1][j-1]);
                func[i][j] = triangle.get(i).get(j) + temp;
            }
        }
        int ans = func[size-1][0];
        for (int i = 0; i < size; i++) {
            ans = Math.min(ans, func[size-1][i]);
        }

        return ans;
    }
    /**
     * 42. 接雨水
     * @param height
     * @return
     */
    public int trap(int[] height) {
        int n = height.length;
        int maxHeight = height[0], indexOfMax = 0;
        for (int i = 0; i < n; i++) {
            if (height[i] > maxHeight){
                maxHeight = height[i];
                indexOfMax = i;
            }
        }
        int trap = 0;
        maxHeight = height[0];
        for (int i = 0; i < indexOfMax; i++) {
            if (height[i] > maxHeight)
                maxHeight = height[i];
            else{
                trap += maxHeight - height[i];
            }
        }
        maxHeight = height[n-1];
        for (int i = n-1; i > indexOfMax; i--) {
            if (height[i] > maxHeight)
                maxHeight = height[i];
            else{
                trap += maxHeight - height[i];
            }
        }
        return trap;
    }

    /**
     * 139. 单词拆分
     * @param s
     * @param wordDict
     * @return
     */
    public boolean wordBreak(String s, List<String> wordDict) {
        Set<String> wordDictSet = new HashSet(wordDict);

        boolean[] dp = new boolean[s.length() + 1];
        dp[0] = true;
        for (int i = 1; i <= s.length(); i++) {
            for (int j = 0; j < i; j++) {
                if (dp[j] && wordDictSet.contains(s.substring(j, i))) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[s.length()];
    }

    /**
     * 714. 买卖股票的最佳时机含手续费
     * @param prices
     * @param fee
     * @return
     */
    public int maxProfitCharge(int[] prices, int fee) {
        int buy = -prices[0], sell = 0;
        for (int i = 1; i < prices.length; i++) {
            buy = Math.max(buy, sell - prices[i]);
            sell = Math.max(sell, buy + prices[i] - fee);
        }
        return sell;
    }

    /**
     * 188. 买卖股票的最佳时机4
     * 最多可以进行k次交易
     * @param k
     * @param prices
     * @return
     */
    public int maxProfit4(int k, int[] prices) {
        int n = prices.length;
        if (n < 2 || k == 0)
            return 0;
        int[] buy = new int[k];
        int[] sell = new int[k];
        Arrays.fill(buy, -prices[0]);
        Arrays.fill(sell,0);
        int buy1 = -prices[0], sell1 = 0;
        int buy2 = -prices[0], sell2 = 0;
        for (int i = 1; i < n; ++i) {
            buy[0] = Math.max(buy[0], -prices[i]);
            sell[0] = Math.max(sell[0], buy[0] + prices[i]);
            for (int j = 1; j < k; j++) {
                buy[j] = Math.max(buy[j], sell[j-1] - prices[i]);
                sell[j] = Math.max(sell[j], buy[j] + prices[i]);
            }
        }
        return sell[k-1];
    }

    /**
     * 123. 买卖股票的最佳时机3：
     * 最多可以购买两次
     * @param prices
     * @return
     */
    public int maxProfit33(int[] prices) {
        int n = prices.length;
        int buy1 = -prices[0], sell1 = 0;
        int buy2 = -prices[0], sell2 = 0;
        for (int i = 1; i < n; ++i) {
            buy1 = Math.max(buy1, -prices[i]);
            sell1 = Math.max(sell1, buy1 + prices[i]);
            buy2 = Math.max(buy2, sell1 - prices[i]);
            sell2 = Math.max(sell2, buy2 + prices[i]);
        }
        return sell2;
    }
    public int maxProfit3(int[] prices) {
        int[] arr = getMaxProfitOpp(prices);
        int profit = 0;
        if (arr[0] > 0){
            int[] prices1 = Arrays.copyOfRange(prices,0, arr[0]);
            int[] arr1 = getMaxProfitOpp(prices1);
            profit = arr1[2];
        }
        if (arr[1] < prices.length-1){
            int[] prices2 = Arrays.copyOfRange(prices,arr[1]+1, prices.length);
            int[] arr2 = getMaxProfitOpp(prices2);
            profit = Math.max(profit,arr2[2]);
        }
        if (arr[0] < arr[1]){
            int[] prices3 = Arrays.copyOfRange(prices,arr[0]+1, arr[1]);
            for (int i = 0; i < prices3.length; i++) {
                prices3[i] = - prices3[i];
            }
            int[] arr3 = getMaxProfitOpp(prices3);
            profit = Math.max(profit, arr3[2]);
        }
        return arr[2] + profit;
    }
    //最多购买一次时，返回最大利润，买入时机，卖出时机
    int[] getMaxProfitOpp(int[] prices){
        int buy = 0, sell = 0;
        if (prices == null || prices.length <= 1){
            return new int[]{0,0,0};
        }
        int minPrice = prices[0], profit = 0, numOfMin = 0;
        for (int i = 0; i < prices.length; i++) {
            int price = prices[i];
            if (price < minPrice) {
                numOfMin = i;
                minPrice = price;
            } else if (price - minPrice > profit) {
                profit = price - minPrice;
                buy = numOfMin;
                sell = i;
            }
        }
        return new int[]{buy, sell, profit};
    }
    /**
     * 309. 最佳买卖股票时机含冷冻期
     * @param prices
     * @return
     */
    public int maxProfitFreezing(int[] prices) {
        int len = prices.length;
        int[] profit = new int[len];//在第i天必须卖出股票的情况下，截止第i天能获得的最大收益
        int[] maxPro = new int[len];//截止第i天能获得的最大收益
        maxPro[0] = 0;
        for (int i = 1; i < 4 && i < len; i++) {
            profit[i] = prices[i] - prices[i-1] + Math.max(profit[i-1],0);
            maxPro[i] = Math.max(maxPro[i-1], profit[i]);
        }
        for (int i = 4; i < len; i++) {
            profit[i] = prices[i] - prices[i-1] +
                    Math.max(Math.max(profit[i-1], maxPro[i-3]),0);
            maxPro[i] = Math.max(maxPro[i], profit[i]);
        }
        return maxPro[len - 1];
    }

    /**
     * 713. 乘积小于k的子数组
     * @param nums
     * @param k
     * @return
     */
    public int numSubarrayProductLessThanK(int[] nums, int k) {
        if (k <= 1) return 0;
        int prod = 1, ans = 0, left = 0;
        for (int right = 0; right < nums.length; right++) {
            prod *= nums[right];
            while (prod >= k) prod /= nums[left++];
            ans += right - left + 1;
        }
        return ans;
    }

    /**
     * 438. 找到字符串中所有字母异位词
     * @param s
     * @param p
     * @return
     */
    public List<Integer> findAnagrams(String s, String p) {
        int len = p.length();
        int lenS = s.length();
        List<Integer> list = new ArrayList<Integer>();
        if (len > lenS)
            return list;
        HashMap<Character, Integer> map = new HashMap<>();
        for (int i = 0; i < len; i++) {
            Character c = p.charAt(i);
            if (map.containsKey(c))
                map.replace(c, map.get(c)+1);
            else
                map.put(c, 1);
        }
        for (int i = 0; i < len; i++) {
            Character c = s.charAt(i);
            if (p.contains(c.toString())){
                if (map.containsKey(c)){
                    if (map.get(c) == 1)
                        map.remove(c);
                    else
                        map.replace(c, map.get(c)-1);
                }else {
                    map.put(c,-1);
                }
            }
        }
        if (map.isEmpty())
            list.add(0);
        int left = 0, right = len;
        while (right < lenS){
            Character c = s.charAt(left);
            if (p.contains(c.toString())){
                if (map.containsKey(c)){
                    if (map.get(c) == -1){
                        map.remove(c);
                    }else {
                        map.replace(c, map.get(c)+1);
                    }
                }else
                    map.put(c,1);
            }
            left++;
            c = s.charAt(right);
            if (p.contains(c.toString())){
                if (map.containsKey(c)){
                    if (map.get(c) == 1)
                        map.remove(c);
                    else
                        map.replace(c, map.get(c)-1);
                }else {
                    map.put(c,-1);
                }
            }
            right++;

            if (map.isEmpty())
                list.add(left);
        }
        return list;
    }

    /**
     * 1567. 乘积为正数的最长子数组长度
     * @param nums
     * @return
     */
    public int getMaxLen(int[] nums) {
        int len = nums.length;
        if (len == 1)
            return nums[0] > 0 ? 1 : 0;
        int maxPos = nums[0] > 0 ? 1 : 0;
        int maxNeg = nums[0] < 0 ? 1 : 0;
        int maxLen = maxPos;
        for (int i = 1; i < len; i++) {

            if (nums[i] == 0){
                maxNeg = maxPos = 0;
            }else if (nums[i] > 0){
                maxPos++;
                if (maxNeg > 0)
                    maxNeg++;
            }else {
                int mp = maxPos, mn = maxNeg;
                maxNeg = mp + 1;
                if (mn > 0)
                    maxPos = mn + 1;
                else
                    maxPos = 0;
            }
            maxLen = Math.max(maxLen, maxPos);
        }
        return maxLen;
    }

    /**
     * 152. 乘积最大子数组
     * @param nums
     * @return
     */
    public int maxProduct(int[] nums) {
        int len = nums.length;
        if (len == 1){
            return nums[0];
        }
        int[] maxPos = new int[len];
        int[] maxNeg = new int[len];
        maxPos[0] = maxNeg[0] = nums[0];
        int maxNumber = maxPos[0];
        for (int i = 1; i < len; i++) {
            maxPos[i] = Math.max(Math.max(nums[i], nums[i]* maxPos[i-1]), nums[i] * maxNeg[i-1]);
            maxNeg[i] = Math.min(Math.min(nums[i], nums[i]* maxPos[i-1]), nums[i] * maxNeg[i-1]);
            maxNumber = Math.max(maxNumber, maxPos[i]);
        }
        return maxNumber;
    }

    /**
     * 918. 环形子数组的最大和
     * @param A
     * @return
     */
    public int maxSubarraySumCircular(int[] A) {
        int N = A.length;

        int ans = A[0], cur = A[0];
        for (int i = 1; i < N; ++i) {
            cur = A[i] + Math.max(cur, 0);
            ans = Math.max(ans, cur);
        }

        // rightsums[i] = A[i] + A[i+1] + ... + A[N-1]
        int[] rightsums = new int[N];
        rightsums[N-1] = A[N-1];
        for (int i = N-2; i >= 0; --i)
            rightsums[i] = rightsums[i+1] + A[i];

        // maxright[i] = max_{j >= i} rightsums[j]
        int[] maxright = new int[N];
        maxright[N-1] = A[N-1];
        for (int i = N-2; i >= 0; --i)
            maxright[i] = Math.max(maxright[i+1], rightsums[i]);

        int leftsum = 0;
        for (int i = 0; i < N-2; ++i) {
            leftsum += A[i];
            ans = Math.max(ans, leftsum + maxright[i+2]);
        }
        return ans;
    }
    /**
     * 53. 最大子数组和
     * @param nums
     * @return
     */
    public int maxSubArray(int[] nums) {
        int[] func = new int[nums.length];
        func[0] = nums[0];
        int maxArr = func[0];
        for (int i = 1; i < nums.length; i++) {
            func[i] = Math.max(nums[i], func[i-1] + nums[i]);
            maxArr = Math.max(maxArr, func[i]);
        }
        return maxArr;
    }

    /*
    46. 全排列
     */
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> list = new ArrayList<>();
        if (nums.length == 1){
            List<Integer> list1 = new ArrayList<>();
            list1.add(nums[0]);
            list.add(list1);
            return list;
        }
        List<Integer> ints = Arrays.stream(nums).boxed().collect(Collectors.toList());
        return Backtracking(ints);
    }
    List<List<Integer>> Backtracking(List<Integer> nums){
        List<List<Integer>> list = new ArrayList<>();
        if (nums.size()== 1){
            List<Integer> list1 = new ArrayList<>();
            list1.add(nums.get(0));
            list.add(list1);
            return list;
        }
        for (int i = 0; i < nums.size(); i++) {
            int temp = nums.remove(i);
            List<List<Integer>> list1 = Backtracking(nums);
            for (var list2 : list1) {
                list2.add(temp);
            }
            list.addAll(list1);
            nums.add(i,temp);
        }
        return list;
    }

    /*
    45. 跳跃游戏2
     */
    public int jump2(int[] nums) {
        int length = nums.length;
        int end = 0;
        int maxPosition = 0;
        int steps = 0;
        for (int i = 0; i < length - 1; i++) {
            maxPosition = Math.max(maxPosition, i + nums[i]);
            if (i == end) {//到达边界
                end = maxPosition;
                steps++;
            }
        }
        return steps;
    }
    public int jump(int[] nums) {
        int skips = 0;
        int position = 0;
        int n = nums.length;
        while (position < n - 1) {
            int maxArrive = 0, distance = 0;
            if (position + nums[position] >= n - 1) {
                return skips + 1;
            }
            for (int i = position; i <= position + nums[position]; i++) {

                if (maxArrive <= i + nums[i]) {
                    maxArrive = i + nums[i];
                    distance = i;
                }
            }
            ++skips;
            position = distance;
        }
        return skips;
    }

    /*
    55. 跳跃游戏
     */
    public boolean canJump(int[] nums) {
//        boolean[] isArrive = new boolean[nums.length];
//        isArrive[0] = true;
        int maxArrive = 0;
        for (int i = 0; i < nums.length; i++) {
            if (i <= maxArrive) {
                maxArrive = Math.max(maxArrive, i + nums[i]);
                if (maxArrive >= nums.length - 1)
                    return true;
            } else
                return false;
        }
        return true;
    }

    /*
    844. 比较含退格的字符串
     */
    public boolean backspaceCompare(String s, String t) {
        ArrayList<Character> list1 = new ArrayList<>();
        ArrayList<Character> list2 = new ArrayList<>();
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            if (ch == '#') {
                if (list1.size() > 0)
                    list1.remove(list1.size() - 1);
            } else
                list1.add(ch);
        }
        String s1 = list1.toString();

        for (int i = 0; i < t.length(); i++) {
            char ch = t.charAt(i);
            if (ch == '#') {
                if (list2.size() > 0)
                    list2.remove(list2.size() - 1);
            } else
                list2.add(ch);
        }
        String s2 = list2.toString();

        return s1.equals(s2);
    }

    /*
    740. 删除并获得点数
     */
    public int deleteAndEarn(int[] nums) {
        if (nums.length == 1)
            return nums[0];
        int maxVal = 0;
        for (int val : nums) {
            maxVal = Math.max(maxVal, val);
        }
        int[] vals = new int[maxVal + 1];
        for (int val : nums) {
            vals[val] += val;
        }
        return rob(vals);
    }

    /**
    213. 打家劫舍2
     */
    public int rob2(int[] nums) {
        int len = nums.length;
        if (len == 1) {
            return nums[0];
        } else if (len == 2)
            return Math.max(nums[0], nums[1]);

        int[] copy1 = Arrays.copyOfRange(nums, 0, len - 1);
        int result1 = rob(copy1);
        copy1 = Arrays.copyOfRange(nums, 1, len);
        int result2 = rob(copy1);

        return Math.max(result1, result2);
    }

    /*
    198. 打家劫舍
     */
    public int rob(int[] nums) {
        int length = nums.length;
        if (length == 1) {
            return nums[0];
        }
        int[] result = new int[length];
        result[0] = nums[0];
        result[1] = Math.max(nums[0], nums[1]);
        for (int i = 2; i < length; i++) {
            result[i] = Math.max(result[i - 1], result[i - 2] + nums[i]);
        }
        return result[length - 1];
    }

    /*
    15 三数之和
     */
    public List<List<Integer>> threeSum(int[] nums) {
        int n = nums.length;

        Arrays.sort(nums);
        List<List<Integer>> list = new ArrayList<List<Integer>>();
        int a = 0, b, c;
        while (a < n - 2) {
            int target = -nums[a];
            b = a + 1;
            c = n - 1;
            while (b < c) {
                if (nums[b] + nums[c] == target) {
                    List<Integer> list1 = Arrays.asList(nums[a], nums[b], nums[c]);
                    list.add(list1);
                }
                if (nums[b] + nums[c] >= target) {
                    c--;
                    while (c > 0 && nums[c] == nums[c + 1]) {
                        c--;
                    }
                } else if (nums[b] + nums[c] <= target) {
                    b++;
                    while (b < n - 1 && nums[b] == nums[b - 1])
                        b++;
                }
            }
            a++;
            while (a < n - 1 && nums[a] == nums[a - 1])
                a++;
        }
        return list;
    }

    /*
    82. 删除排序链表中的重复元素
     */
    public ListNode deleteDuplicates(ListNode head) {
        ListNode dummy = new ListNode(-101, head);
        ListNode left = dummy, right = head;
        while (right != null && right.next != null) {
            if (right.val == right.next.val) {
                while (right.next != null && right.val == right.next.val) {
                    right = right.next;
                }
                left.next = right.next;
                right = left.next;
            } else {
                right = right.next;
                left = left.next;
            }
        }
        return dummy.next;
    }

    /*
    搜索二维矩阵
     */
    public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length;
        int n = matrix[0].length;
        int left = 0, right = m * n - 1;
        int result = -1;
        while (left <= right) {
            int mid = (left + right) / 2;
            int i = mid / n;
            int j = mid - i * n;
            if (matrix[i][j] == target) {
                result = mid;
                break;
            } else if (matrix[i][j] > target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }

        return result != -1;
    }

    /*
    39. 组合总和 回溯算法
     */
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> ans = new ArrayList<List<Integer>>();
        List<Integer> combine = new ArrayList<Integer>();
        dfs(candidates, target, ans, combine, 0);
        return ans;
    }

    void dfs(int[] candidates, int target, List<List<Integer>> ans, List<Integer> combine, int idx) {
        if (idx == candidates.length) {
            return;
        }
        if (target == 0) {
            ans.add(new ArrayList<Integer>(combine));
            return;
        }
        if (target < 0) {
            return;
        }
        // 直接跳过
        dfs(candidates, target, ans, combine, idx + 1);
        // 选择当前数
        if (target - candidates[idx] >= 0) {
            combine.add(candidates[idx]);
            dfs(candidates, target - candidates[idx], ans, combine, idx);
            combine.remove(combine.size() - 1);
        }
    }

    /*
    34. 在排序数组中查找元素的第一个和最后一个位置
     */
    public int[] searchRange(int[] nums, int target) {
        int[] range = new int[2];
        int index = Arrays.binarySearch(nums, 0, nums.length, target);
        if (index == -1) {
            range[0] = -1;
            range[1] = -1;
        }
        int left = index, right = index;
        while (left >= 0 && nums[left] == target) {
            left--;
        }
        while (right < nums.length && nums[right] == target) {
            right++;
        }
        range[0] = left + 1;
        range[1] = right - 1;
        return range;
    }

    /*
    33 搜索旋转数组 直接二分查找
     */
    public int search2(int[] nums, int target) {
        int n = nums.length;
        if (n == 0) {
            return -1;
        }
        if (n == 1) {
            return nums[0] == target ? 0 : -1;
        }
        int l = 0, r = n - 1;
        while (l <= r) {
            int mid = (l + r) / 2;
            if (nums[mid] == target) {
                return mid;
            }
            if (nums[0] <= nums[mid]) {
                if (nums[0] <= target && target < nums[mid]) {
                    r = mid - 1;
                } else {
                    l = mid + 1;
                }
            } else {
                if (nums[mid] < target && target <= nums[n - 1]) {
                    l = mid + 1;
                } else {
                    r = mid - 1;
                }
            }
        }
        return -1;
    }

    /*
    33 搜索旋转数组
     */
    public int search(int[] nums, int target) {
        int n = nums.length;
        int a = nums[0], left = 0, right = n - 1;
        if (nums[n - 1] >= a) {
            return midSearch(nums, 0, n - 1, target);
        }
        while (right - left > 1) {
            int mid = (left + right) / 2;
            if (nums[mid] >= a) {
                left = mid;
            } else {
                right = mid;
            }
        }
        if (target > nums[0]) {
            return midSearch(nums, 0, right - 1, target);
        } else {
            return midSearch(nums, right, n - 1, target);
        }
    }

    int midSearch(int[] nums, int low, int high, int target) {
        while (low <= high) {
            int middle = (low + high) / 2;
            if (nums[middle] > target) {
                //比关键字大则关键字在左区域
                high = middle - 1;
            } else if (nums[middle] < target) {
                //比关键字小则关键字在右区域
                low = middle + 1;
            } else {
                return middle;
            }
        }
        return -1;
    }

    /*
    32 最长有效括号 栈， 栈底为 最后一个没有被匹配的右括号的下标
     */
    public int longestValidParentheses2(String s) {
        int maxans = 0;
        Deque<Integer> stack = new LinkedList<Integer>();
        stack.push(-1);
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                stack.push(i);
            } else {
                stack.pop();
                if (stack.isEmpty()) {
                    stack.push(i);
                } else {
                    maxans = Math.max(maxans, i - stack.peek());
                }
            }
        }
        return maxans;
    }

    /*
    32 最长有效括号 自己做的
     */
    public int longestValidParentheses(String s) {
        Deque<Integer> stack = new ArrayDeque<>();
        int n = s.length();
        boolean[] isValid = new boolean[n];
        int maxLength = 0, length = 0;
        for (int i = 0; i < n; i++) {
            if (s.charAt(i) == '(') {
                stack.push(i);
            } else {
                if (stack.isEmpty()) {
                } else {
                    int a = stack.pop();
                    isValid[a] = true;
                    isValid[i] = true;
                }
            }
        }
        for (int i = 0; i < n; i++) {
            if (isValid[i]) {
                length++;
                maxLength = Math.max(maxLength, length);
            } else if (length > 0) {
                maxLength = Math.max(maxLength, length);
                length = 0;
            }
        }
        return maxLength;
    }

    /*
    31 下一个排列
     */
    public void nextPermutation2(int[] nums) {
        int i = nums.length - 2;
        while (i >= 0 && nums[i] >= nums[i + 1]) {
            i--;
        }
        if (i >= 0) {
            int j = nums.length - 1;
            while (j >= 0 && nums[i] >= nums[j]) {
                j--;
            }
            swap(nums, i, j);
        }
        reverse(nums, i + 1);
    }

    void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    void reverse(int[] nums, int start) {
        int left = start, right = nums.length - 1;
        while (left < right) {
            swap(nums, left, right);
            left++;
            right--;
        }
    }

    public void nextPermutation(int[] nums) {
        int n = nums.length;
        int i;
        for (i = n - 1; i > 0; i--) {
            if (nums[i] > nums[i - 1]) {
                int k = i;
                while (k < n && nums[i - 1] < nums[k]) {
                    k++;
                }
                int temp = nums[i - 1];
                nums[i - 1] = nums[k - 1];
                nums[k - 1] = temp;

                Arrays.sort(nums, i, n);
                break;
            }
        }
        if (i == 0) {
            Arrays.sort(nums);
        }
    }

    /*
    23 合并k个字符串 分治合并
     */
    public ListNode mergeKLists2(ListNode[] lists) {

        return merge(lists, 0, lists.length - 1);
    }

    ListNode merge(ListNode[] lists, int start, int end) {
        if (end - start < 0)
            return null;
        else if (end - start == 0)
            return lists[start];
        else if (end - start == 1)
            return mergeTwoLists(lists[start], lists[end]);

        int mid = (end + start) >> 1;
        return mergeTwoLists(merge(lists, start, mid), merge(lists, mid + 1, end));
    }

    /*
    23 合并k个字符串 优先队列
     */
    public ListNode mergeKLists(ListNode[] lists) {
        Queue<ListNode> pq = new PriorityQueue<>((v1, v2) -> v1.val - v2.val);
        for (ListNode node : lists) {
            if (node != null) {
                pq.offer(node);
            }
        }

        ListNode dummyHead = new ListNode(0);
        ListNode tail = dummyHead;
        while (!pq.isEmpty()) {
            ListNode minNode = pq.poll();
            tail.next = minNode;
            tail = minNode;
            if (minNode.next != null) {
                pq.offer(minNode.next);
            }
        }

        return dummyHead.next;
    }

    /*
    21 合并两个有序链表
     */
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) {
            return l2;
        } else if (l2 == null) {
            return l1;
        } else if (l1.val < l2.val) {
            l1.next = mergeTwoLists(l1.next, l2);
            return l1;
        } else {
            l2.next = mergeTwoLists(l1, l2.next);
            return l2;
        }
    }

    /*22 括号的生成 按长度递归*/
    ArrayList[] cache = new ArrayList[100];

    public List<String> generateParenthesis3(int n) {
        return generate(n);
    }

    List<String> generate(int n) {
        if (cache[n] != null) {
            return cache[n];
        }
        ArrayList<String> ans = new ArrayList<String>();
        if (n == 0) {
            ans.add("");
        } else {
            for (int c = 0; c < n; ++c) {
                for (String left : generate(c)) {
                    for (String right : generate(n - 1 - c)) {
                        ans.add("(" + left + ")" + right);
                    }
                }
            }
        }
        cache[n] = ans;
        return ans;
    }


    /*22 括号的生成 回溯算法*/
    public List<String> generateParenthesis2(int n) {

        List<String> ans = new ArrayList<String>();
        backtrack(ans, new StringBuilder(), 0, 0, n);
        return ans;
    }

    void backtrack(List<String> ans, StringBuilder cur, int open, int close, int max) {
        if (cur.length() == max * 2) {
            ans.add(cur.toString());
            return;
        }
        if (open < max) {
            cur.append('(');
            backtrack(ans, cur, open + 1, close, max);
            cur.deleteCharAt(cur.length() - 1);
        }
        if (close < open) {
            cur.append(')');
            backtrack(ans, cur, open, close + 1, max);
            cur.deleteCharAt(cur.length() - 1);
        }
    }

    /*22 括号的生成 递归算法*/
    public List<String> generateParenthesis(int n) {

        List<String> list = new ArrayList<>();
        addLeftParenthesis(list, "", n - 1, n);

        return list;
    }

    void addLeftParenthesis(List<String> list, String s, int left, int right) {
        s = s + "(";
        if (left > 0)
            addLeftParenthesis(list, s, left - 1, right);
        if (left < right)
            addRightParenthesis(list, s, left, right - 1);
    }

    void addRightParenthesis(List<String> list, String s, int left, int right) {
        s = s + ")";
        if (left > 0)
            addLeftParenthesis(list, s, left - 1, right);
        if (left < right)
            addRightParenthesis(list, s, left, right - 1);
        if (right == 0)
            list.add(s);
    }
}

